import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Sort {
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while(gap != 1) {
            gap /= 2;
            shell(arr, gap);
        }
    }

    private static void shell(int[] arr, int gap) {
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if(tmp >= arr[j]) {
                    break;
                } else {
                    arr[j + gap] = arr[j];
                }
            }
            arr[j + gap] = tmp;
        }
    }

    // 选择排序
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
        }
    }

    // 堆排序
    public static void heapSort(int[] array) {
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            siftDown(array, 0, end);
            end--;
        }
    }

    public static void createHeap(int[] arr) {
        for (int parent = (arr.length - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(arr, parent, arr.length);
        }
    }

    private static void siftDown(int[] array, int parent, int len) {
        int child = parent * 2 + 1;
        while (child < len) {
            if (child + 1 < len && array[child + 1] > array[child]) {
                child++;
            }
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flg = true;
                }
            }
            if(!flg) {
                break;
            }
        }
    }

    // 快速
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        if(left >= right) {
            return;
        }

        // 优化 1
        if(right - left + 1 <= 15) {
            bubbleSort(array);
        }

        // 优化 2 --> 减少递归层次
        int mid = (right - left) / 2 + left;
        int index = getIndexOfMidNum(array, left, mid, right);
        swap(array, index, left);

//        int pivot = partitionHoare(array, left, right);
        int pivot = partitionHold(array, left, right);
//        int pivot = partitionPointer(array, left, right);


        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }

    /**
     * 获得中间数
     */
    private static int getIndexOfMidNum(int[] array, int left, int mid, int right) {
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            } else if(array[right] < array[mid]) {
                return right;
            } else {
                return mid;
            }
        } else {
            // array[left] > array[right]
            if(array[mid] > array[left]) {
                return left;
            } else if(array[right] > array[mid]) {
                return right;
            } else {
                return mid;
            }
        }
    }

    // 快速 -- 前后指针
    private static int partitionPointer(int[] array, int left, int right) {
        int cur = left + 1;
        int prev = left;
        while(cur <= right) {
            // prev 是较小范围的最后一个
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, prev, cur);
            }
            cur++;
        }
        swap(array, prev, left);
        return prev;
    }

    // 快速 -- 挖洞法
    private static int partitionHold(int[] array, int left, int right) {
        int tmp = array[left];
        while(left < right) {
            while(left < right && tmp <= array[right]) {
                right--;
            }
            array[left] = array[right];
            while(left < right && tmp >= array[left]) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    // 快速 -- Hoare
    private static int partitionHoare(int[] array, int left, int right) {
        int head = left;// 第一个的下标
        while(left < right) {
            while(left < right && array[right] >= array[head]) {
                right--;
            }
            while(left < right && array[left] <= array[head]) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, head, left);
        return left;
    }

    /**
     * 非递归快排
     * @param array
     */
    public static void quickSortNor(int[] array) {
        int left = 0;
        int right = array.length - 1;
        Stack<Integer> stack = new Stack<>();
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            int pivot = partitionHoare(array, left, right);

            if(pivot + 1 < right) {
                stack.push(pivot + 1);
                stack.push(right);
            }
            if(left < pivot - 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
        }
    }

    /**
     * 归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if(left >= right) {
            return;
        }

        // 分
        int mid = (right - left) / 2 + left;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 排
        merge(arr, left, mid, right);
    }

    /**
     * 非递归 归并
     * @param arr
     */
    public static void mergeSortNor(int[] arr) {
        int gap = 1;
        while(gap < arr.length) {
            gap *= 2;
            for (int i = 0; i < arr.length; i += gap) {
                int right = i + gap - 1;
                int mid = (right - i) / 2 + i;
                // 防止越界
                if(right >= arr.length) {
                    right = arr.length - 1;
                }
                if(mid >= arr.length) {
                    mid = arr.length - 1;
                }
                merge(arr, i, mid, right);
            }
        }
    }


    /**
     * 第一段有序的范围是 [left, mid]
     * 第二段有序的范围是 [mid + 1, right]
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] tmpArr = new int[right - left + 1];

        int s1 = left;
        int s2 = mid + 1;
        int indexArr = 0;

        while(s1 <= mid && s2 <= right) {
            if(arr[s1] < arr[s2]) {
                tmpArr[indexArr++] = arr[s1++];
            } else {
                tmpArr[indexArr++] = arr[s2++];
            }
        }

        while(s1 <= mid) {
            tmpArr[indexArr++] = arr[s1++];
        }

        while(s2 <= right) {
            tmpArr[indexArr++] = arr[s2++];
        }

        indexArr = 0;
        // 拷贝
        for (int i = left; i <= right; i++) {
            arr[i] = tmpArr[indexArr++];
        }
    }

    /**
     * 获取最小/最大值
     * 下标 0   1
     */
    private static int[] getMinAndMax(int[] arr) {
        int[] ret = {arr[0], arr[0]};
        for (int i = 1; i < arr.length; i++) {
            if(ret[0] > arr[i]) {
                ret[0] = arr[i];
            }
            if(ret[1] < arr[i]) {
                ret[1] = arr[i];
            }
        }
        return ret;
    }

    /**
     * 计数排序
     * @param arr
     */
    public static void countSort(int[] arr) {
        int[] nums = getMinAndMax(arr);
        int[] tmpArr = new int[nums[1] - nums[0] + 1];

        for (int i = 0; i < arr.length; i++) {
            tmpArr[arr[i] - nums[0]]++;
        }

        int index = 0;
        for (int i = 0; i < tmpArr.length; i++) {
            while(tmpArr[i]-- > 0) {
                arr[index++] = i + nums[0];
            }
        }
    }

    /**
     * 基数排序
     * @param arr
     */
    public static void baseSort(int[] arr) {
        baseSort(arr, 10);
    }

    // type 表示这个是 多少 进制
    public static void baseSort(int[] arr, int type) {
        List<List<Integer>> list = createList(type);
        int maxLen = getMaxLen(arr);
        for (int i = 1; i <= maxLen; i++) {
            // 添加
            for (int j = 0; j < arr.length; j++) {
                int index = getValueOfDigital(arr[j], i);
                list.get(index).add(arr[j]);
            }
            // 拷贝
            int index = 0;
            for (int j = 0; j < type; j++) {
                List<Integer> list1 = list.get(j);
                while(!list1.isEmpty()) {
                    arr[index++] = list1.remove(0);
                }
            }
        }
    }

    // 创建长度为 len 的列表
    private static List<List<Integer>> createList(int len) {
        // 外部是 ArrayList 内部是 LinkedList
        List<List<Integer>> list = new ArrayList<>(len);
        for (int i = 0; i < len; i++) {
            list.add(new LinkedList<>());
        }
        return list;
    }

    /**
     * 得到该数组中最大值的长度
     */
    private static int getMaxLen(int[] arr) {
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            int num = Math.abs(arr[i]);
            if(max < num) {
                max = num;
            }
        }

        int len = 0;
        while(max != 0) {
            max /= 10;
            len++;
        }

        return len;
    }

    /**
     * 得到 数位 所对应的值
     * @param num 数字
     * @param digital 对应的数位
     */
    private static int getValueOfDigital(int num, int digital) {
        return num / (int)Math.pow(10, digital - 1) % 10;        
    }


    public static void bucketSort(int[] arr) {
        int[] nums = getMinAndMax(arr);

        int len = 10;
        List<List<Integer>> list = createList(len);

        // 添加
        for (int i = 0; i < arr.length; i++) {
            addNum(list, arr[i], nums[0], nums[1]);
        }

        // 排序
        for (int i = 0; i < len; i++) {
            list.get(i).sort(((o1, o2) -> o1.compareTo(o2)));
        }

        // 拷贝
        int index = 0;
        for (int i = 0; i < len; i++) {
            List<Integer> list1 = list.get(i);
            while(!list1.isEmpty()) {
                arr[index++] = list1.remove(0);
            }
        }
    }

    private static void addNum(List<List<Integer>> list, int num, int min, int max) {
        int len = list.size();
        int unit = (max - min) * len;
        int index = 0;

        // [10,20), [20,30) ... [100,110]
        for (; index < len - 1; index++) {
            if(index * unit + min <= num && num < (index + 1) * unit + min) {
                break;
            }
        }
        // 此时 index 所对应的就是 num 应该存放的空间
        list.get(index).add(num);
    }
}
